//
// Created by Administrator on 2021/6/30.
//
#include <vector>
#include <iostream>

using namespace std;

class Solution {
private:
    const vector<vector<int>> move{{0,  1},
                             {0,  -1},
                             {1,  0},
                             {-1, 0}};
public:
    int islandPerimeter(vector<vector<int>> &grid) {
        /**
         * 对于每一块陆地,判断它的四条边是否形成周长:是边界或者旁边是水
         * 可以直接遍历所有格子,如果是陆地再进行判断
         * 或者dfs/bfs 只找陆地进行判断(需要标记)
         */
        auto m = grid.size();
        auto n = grid[0].size();
        int ans = 0;
        // 遍历格子
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 是陆地
                if (grid[i][j] == 1) {
                    // 找四个方向
                    int count = 0;
                    for (int k = 0; k < 4; ++k) {
                        int nextX = i + move[k][0];
                        int nextY = j + move[k][1];
                        // 判断这条边是不是周长的边
                        if (nextX < 0 or nextX >= m or nextY < 0 or nextY >= n or grid[nextX][nextY] == 0)
                            ++count;
                    }
                    ans += count;
                }
            }
        }
        return ans;
    }
};
class Solution2 { // 题解 dfs
    constexpr static int dx[4] = {0, 1, 0, -1};
    constexpr static int dy[4] = {1, 0, -1, 0};
public:
    int dfs(int x, int y, vector<vector<int>> &grid, int n, int m) {
        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
            return 1;
        }
        if (grid[x][y] == 2) {
            return 0;
        }
        grid[x][y] = 2; // 标记为搜索过
        int res = 0;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            res += dfs(tx, ty, grid, n, m);
        }
        return res;
    }
    int islandPerimeter(vector<vector<int>> &grid) {
        int n = grid.size(), m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                // 如果有多个岛屿,也可以计算
                if (grid[i][j] == 1) {
                    ans += dfs(i, j, grid, n, m);
                }
            }
        }
        return ans;
    }
};

int main() {
    vector<vector<int>> grid{{0, 1, 0, 0},
                             {1, 1, 1, 0},
                             {0, 1, 0, 0},
                             {1, 1, 0, 0}};
    Solution2 sol;
    cout << sol.islandPerimeter(grid) << endl;
    return 0;
}